SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Parallel programming model</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Parallel programming model</span></span>

</h1>

</header>

<p>In <a href="Computing" title="Computing">computing</a>, a <b>parallel programming model</b> is an <a href="Abstraction_(software_engineering)" class="mw-redirect" title="Abstraction (software engineering)">abstraction</a> of <a href="Parallel_computing" title="Parallel computing">parallel computer</a> architecture, with which it is convenient to express <a href="Algorithms" class="mw-redirect" title="Algorithms">algorithms</a> and their composition in <a href="Computer_program" title="Computer program">programs</a>. The value of a programming model can be judged on its <i>generality</i>: how well a range of different problems can be expressed for a variety of different architectures, and its <i>performance</i>: how efficiently the compiled programs can execute.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The implementation of a parallel programming model can take the form of a <a href="Library_(computing)" title="Library (computing)">library</a> invoked from a <a href="Programming_language" title="Programming language">programming language</a>, as an extension to an existing languages.

</p><p>Consensus around a particular programming model is important because it leads to different parallel computers being built with support for the model, thereby facilitating <a href="Software_portability" title="Software portability">portability</a> of software. In this sense, programming models are referred to as <i><a href="Bridging_model" title="Bridging model">bridging</a></i> between hardware and software.<sup id="cite_ref-Valiant1990_2-0" class="reference"><a href="#cite_note-Valiant1990-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Classification_of_parallel_programming_models">Classification of parallel programming models</h2></div>

<p>Classifications of parallel programming models can be divided broadly into two areas: process interaction and problem decomposition.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-:0_5-0" class="reference"><a href="#cite_note-:0-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading3"><h3 id="Process_interaction">Process interaction</h3></div>

<p>Process interaction relates to the mechanisms by which parallel processes are able to communicate with each other. The most common forms of interaction are shared memory and message passing, but interaction can also be implicit (invisible to the programmer).

</p>

<div class="mw-heading mw-heading4"><h4 id="Shared_memory">Shared memory</h4></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Shared_memory_(interprocess_communication)" class="mw-redirect" title="Shared memory (interprocess communication)">Shared memory (interprocess communication)</a></div>

<p>Shared memory is an efficient means of passing data between processes. In a shared-memory model, parallel processes share a global address space that they read and write to asynchronously. Asynchronous concurrent access can lead to <a href="Race_condition" title="Race condition">race conditions</a>, and mechanisms such as <a href="Lock_(computer_science)" title="Lock (computer science)">locks</a>, <a href="Semaphore_(programming)" title="Semaphore (programming)">semaphores</a> and <a href="Monitor_(synchronization)" title="Monitor (synchronization)">monitors</a> can be used to avoid these. Conventional <a href="Multi-core_processor" title="Multi-core processor">multi-core processors</a> directly support shared memory, which many parallel programming languages and libraries, such as <a href="Cilk_(programming_language)" class="mw-redirect" title="Cilk (programming language)">Cilk</a>, <a href="OpenMP" title="OpenMP">OpenMP</a> and <a href="Threading_Building_Blocks" title="Threading Building Blocks">Threading Building Blocks</a>, are designed to exploit.

</p>

<div class="mw-heading mw-heading4"><h4 id="Message_passing">Message passing</h4></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Message_passing" title="Message passing">Message passing</a></div>

<p>In a message-passing model, parallel processes exchange data through passing messages to one another. These communications can be asynchronous, where a message can be sent before the receiver is ready, or synchronous, where the receiver must be ready. The <a href="Communicating_sequential_processes" title="Communicating sequential processes">Communicating sequential processes</a> (CSP) formalisation of message passing uses synchronous communication channels to connect processes, and led to important languages such as <a href="Occam_(programming_language)" title="Occam (programming language)">Occam</a>, <a href="Limbo_(programming_language)" title="Limbo (programming language)">Limbo</a> and <a href="Go_(programming_language)" title="Go (programming language)">Go</a>. In contrast, the <a href="Actor_model" title="Actor model">actor model</a> uses asynchronous message passing and has been employed in the design of languages such as <a href="D_(programming_language)" title="D (programming language)">D</a>, <a href="Scala_(programming_language)" title="Scala (programming language)">Scala</a> and SALSA.

</p>

<div class="mw-heading mw-heading4"><h4 id="Partitioned_global_address_space">Partitioned global address space</h4></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Partitioned_global_address_space" title="Partitioned global address space">Partitioned global address space</a></div>

<p>Partitioned Global Address Space (PGAS) models provide a middle ground between shared memory and message passing. PGAS provides a global memory address space abstraction that is logically partitioned, where a portion is local to each process. Parallel processes communicate by asynchronously performing operations (e.g. reads and writes) on the global address space, in a manner reminiscent of shared memory models. However by semantically partitioning the global address space into portions with affinity to a particular processes, they allow programmers to exploit <a href="Locality_of_reference" title="Locality of reference">locality of reference</a> and enable efficient implementation on <a href="Distributed_memory" title="Distributed memory">distributed memory</a> parallel computers. PGAS is offered by many parallel programming languages and libraries, such as <a href="Fortran_2008" class="mw-redirect" title="Fortran 2008">Fortran 2008</a>, <a href="Chapel_(programming_language)" title="Chapel (programming language)">Chapel</a>, <a rel="nofollow" class="external text" href="http://upcxx.lbl.gov">UPC++</a>, and <a href="SHMEM" title="SHMEM">SHMEM</a>.

</p>

<div class="mw-heading mw-heading4"><h4 id="Implicit_interaction">Implicit interaction</h4></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Implicit_parallelism" title="Implicit parallelism">Implicit parallelism</a></div>

<p>In an implicit model, no process interaction is visible to the programmer and instead the compiler and/or runtime is responsible for performing it. Two examples of implicit parallelism are with <a href="Domain-specific_language" title="Domain-specific language">domain-specific languages</a> where the concurrency within high-level operations is prescribed, and with <a href="Functional_programming" title="Functional programming">functional programming languages</a> because the absence of <a href="Side_effect_(computer_science)" title="Side effect (computer science)">side-effects</a> allows non-dependent functions to be executed in parallel.<sup id="cite_ref-ParFuncProg_6-0" class="reference"><a href="#cite_note-ParFuncProg-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> However, this kind of parallelism is difficult to manage<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> and functional languages such as <a href="Concurrent_Haskell" title="Concurrent Haskell">Concurrent Haskell</a> and <a href="Concurrent_ML" title="Concurrent ML">Concurrent ML</a> provide features to manage parallelism explicitly and correctly.

</p>

<div class="mw-heading mw-heading3"><h3 id="Problem_decomposition">Problem decomposition</h3></div>

<p>A parallel program is composed of simultaneously executing processes. Problem decomposition relates to the way in which the constituent processes are formulated.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-:0_5-1" class="reference"><a href="#cite_note-:0-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading4"><h4 id="Task_parallelism">Task parallelism</h4></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Task_parallelism" title="Task parallelism">Task parallelism</a></div>

<p>A task-parallel model focuses on processes, or threads of execution. These processes will often be behaviourally distinct, which emphasises the need for communication. Task parallelism is a natural way to express message-passing communication. In <a href="Flynn's_taxonomy" title="Flynn's taxonomy">Flynn's taxonomy</a>, task parallelism is usually classified as <a href="Multiple_instruction%2C_multiple_data" title="Multiple instruction, multiple data">MIMD</a>/<a href="Flynn's_taxonomy#MPMD" title="Flynn's taxonomy">MPMD</a> or <a href="Multiple_instruction%2C_single_data" title="Multiple instruction, single data">MISD</a>.

</p>

<div class="mw-heading mw-heading4"><h4 id="Data_parallelism">Data parallelism</h4></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Data_parallelism" title="Data parallelism">Data parallelism</a></div>

<p>A data-parallel model focuses on performing operations on a data set, typically a regularly structured array. A set of tasks will operate on this data, but independently on disjoint partitions. In <a href="Flynn's_taxonomy" title="Flynn's taxonomy">Flynn's taxonomy</a>, data parallelism is usually classified as <a href="Multiple_instruction%2C_multiple_data" title="Multiple instruction, multiple data">MIMD</a>/<a href="SPMD" class="mw-redirect" title="SPMD">SPMD</a> or <a href="Single_instruction%2C_multiple_data" title="Single instruction, multiple data">SIMD</a>.

</p>

<div class="mw-heading mw-heading4"><h4 id="Stream_Parallelism">Stream Parallelism</h4></div>

<p>Stream parallelism, also known as pipeline parallelism, focuses on dividing a computation

into a sequence of stages, where each stage processes a portion of the input

data. Each stage operates independently and concurrently, and the output of one

stage serves as the input to the next stage. Stream parallelism is particularly suitable

for applications with continuous data streams or pipelined computations.

</p>

<div class="mw-heading mw-heading4"><h4 id="Implicit_parallelism">Implicit parallelism</h4></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Implicit_parallelism" title="Implicit parallelism">Implicit parallelism</a></div>

<p>As with implicit process interaction, an implicit model of parallelism reveals nothing to the programmer as the compiler, the runtime or the hardware is responsible. For example, in compilers, <a href="Automatic_parallelization" title="Automatic parallelization">automatic parallelization</a> is the process of converting sequential code into parallel code, and in computer architecture, <a href="Superscalar_processor" title="Superscalar processor">superscalar execution</a> is a mechanism whereby <a href="Instruction-level_parallelism" title="Instruction-level parallelism">instruction-level parallelism</a> is exploited to perform operations in parallel.

</p>

<div class="mw-heading mw-heading2"><h2 id="Terminology">Terminology</h2></div>

<p>Parallel programming models are closely related to <a href="Model_of_computation" title="Model of computation">models of computation</a>. A model of parallel computation is an <a href="Abstraction" title="Abstraction">abstraction</a> used to analyze the cost of computational processes, but it does not necessarily need to be practical, in that it can be implemented efficiently in hardware and/or software. A programming model, in contrast, does specifically imply the practical considerations of hardware and software implementation.<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup>

</p><p>A parallel programming language may be based on one or a combination of programming models. For example, <a href="High_Performance_Fortran" title="High Performance Fortran">High Performance Fortran</a> is based on shared-memory interactions and data-parallel problem decomposition, and <a href="Go_(programming_language)" title="Go (programming language)">Go</a> provides mechanism for shared-memory and message-passing interaction.

</p>

<div class="mw-heading mw-heading2"><h2 id="Example_parallel_programming_models">Example parallel programming models</h2></div>

<th>Class of interaction</th>

<th>Class of decomposition</th>

<th>Example implementations

</th></tr>

<tr>

<td><a href="Actor_model" title="Actor model">Actor model</a>

</td>

<td>Asynchronous message passing

</td>

<td>Task

</td>

<td><a href="D_(programming_language)" title="D (programming language)">D</a>, <a href="Erlang_(programming_language)" title="Erlang (programming language)">Erlang</a>, <a href="Scala_(programming_language)" title="Scala (programming language)">Scala</a>, SALSA

</td></tr>

<tr>

<td><a href="Bulk_synchronous_parallel" title="Bulk synchronous parallel">Bulk synchronous parallel</a>

</td>

<td>Shared memory

</td>

<td>Task

</td>

<td><a href="Apache_Giraph" title="Apache Giraph">Apache Giraph</a>, <a href="Apache_Hama" title="Apache Hama">Apache Hama</a>, BSPlib

</td></tr>

<tr>

<td><a href="Communicating_sequential_processes" title="Communicating sequential processes">Communicating sequential processes</a>

</td>

<td>Synchronous message passing

</td>

<td>Task

</td>

<td><a href="Ada_(programming_language)" title="Ada (programming language)">Ada</a>, <a href="Occam_(programming_language)" title="Occam (programming language)">Occam</a>, <a href="VerilogCSP" title="VerilogCSP">VerilogCSP</a>, <a href="Go_(programming_language)" title="Go (programming language)">Go</a>

</td></tr>

<tr>

<td><a href="Circuit_(computer_science)" title="Circuit (computer science)">Circuits</a>

</td>

<td>Message passing

</td>

<td>Task

</td>

<td><a href="Verilog" title="Verilog">Verilog</a>, <a href="VHDL" title="VHDL">VHDL</a>

</td></tr>

<tr>

<td><a href="Dataflow_programming" title="Dataflow programming">Dataflow</a>

</td>

<td>Message passing

</td>

<td>Task

</td>

<td><a href="Lustre_(programming_language)" title="Lustre (programming language)">Lustre</a>, <a href="TensorFlow" title="TensorFlow">TensorFlow</a>, <a href="Apache_Flink" title="Apache Flink">Apache Flink</a>

</td></tr>

<tr>

<td><a href="Functional_programming" title="Functional programming">Functional</a>

</td>

<td>Message passing

</td>

<td>Task

</td>

<td><a href="Concurrent_Haskell" title="Concurrent Haskell">Concurrent Haskell</a>, <a href="Concurrent_ML" title="Concurrent ML">Concurrent ML</a>

</td></tr>

<tr>

<td><a href="LogP_machine" title="LogP machine">LogP machine</a>

</td>

<td>Synchronous message passing

</td>

<td>Not specified

</td>

<td>None

</td></tr>

<tr>

<td><a href="Parallel_random_access_machine" class="mw-redirect" title="Parallel random access machine">Parallel random access machine</a>

</td>

<td>Shared memory

</td>

<td>Data

</td>

<td><a href="Cilk_(programming_language)" class="mw-redirect" title="Cilk (programming language)">Cilk</a>, <a href="CUDA" title="CUDA">CUDA</a>, <a href="OpenMP" title="OpenMP">OpenMP</a>, <a href="Threading_Building_Blocks" title="Threading Building Blocks">Threading Building Blocks</a>, <a href="XMTC" title="XMTC">XMTC</a>

</td></tr>

<tr>

</td>

<td>Partitioned global address space

</td>

<td>Data

</td>

<td><a href="Fortran_2008" class="mw-redirect" title="Fortran 2008">Fortran 2008</a>, <a href="Unified_Parallel_C" title="Unified Parallel C">Unified Parallel C</a>, <a rel="nofollow" class="external text" href="http://upcxx.lbl.gov">UPC++</a>, <a href="SHMEM" title="SHMEM">SHMEM</a>

</td></tr>

<tr>

<td>Global-view <a href="Task_parallelism" title="Task parallelism">Task parallelism</a>

</td>

<td>Partitioned global address space

</td>

<td>Task

</td>

<td><a href="Chapel_(programming_language)" title="Chapel (programming language)">Chapel</a>, <a href="X10_(programming_language)" title="X10 (programming language)">X10</a>

</td></tr></tbody></table>

<ul><li><a href="Automatic_parallelization" title="Automatic parallelization">Automatic parallelization</a></li>

<li><a href="Bridging_model" title="Bridging model">Bridging model</a></li>

<li><a href="Concurrent_computing" title="Concurrent computing">Concurrency</a></li>

<li><a href="Degree_of_parallelism" title="Degree of parallelism">Degree of parallelism</a></li>

<li><a href="Explicit_parallelism" title="Explicit parallelism">Explicit parallelism</a></li>

<li><a href="List_of_concurrent_and_parallel_programming_languages" title="List of concurrent and parallel programming languages">List of concurrent and parallel programming languages</a></li>

<li><a href="Optical_Multi-Tree_with_Shuffle_Exchange" title="Optical Multi-Tree with Shuffle Exchange">Optical Multi-Tree with Shuffle Exchange</a></li>

<li><a href="Parallel_external_memory_(Model)" class="mw-redirect" title="Parallel external memory (Model)">Parallel external memory (Model)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Skillicorn, David B., "Models for practical parallel computation", International Journal of Parallel Programming, 20.2 133–158 (1991), <a rel="nofollow" class="external free" href="https://www.ida.liu.se/~chrke55/papers/modelsurvey.pdf">https://www.ida.liu.se/~chrke55/papers/modelsurvey.pdf</a></span>

</li>

<li id="cite_note-Valiant1990-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-Valiant1990_2-0">^</a></b></span> <span class="reference-text">Leslie G. Valiant, "A bridging model for parallel computation", Communications of the ACM, Volume 33, Issue 8, August, 1990, pages 103–111.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">John E. Savage, Models of Computation: Exploring the Power of Computing, 2008, Chapter 7 (Parallel Computation), <a rel="nofollow" class="external free" href="http://cs.brown.edu/~jes/book/">http://cs.brown.edu/~jes/book/</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20161105053330/http://cs.brown.edu/~jes/book/">Archived</a> 2016-11-05 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.mcs.anl.gov/~itf/dbpp/text/node9.html">"1.3 A Parallel Programming Model"</a>. <i>www.mcs.anl.gov</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2024-03-21</span></span>.</cite></span>

</li>

<li id="cite_note-:0-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_5-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://hpc.llnl.gov/documentation/tutorials/introduction-parallel-computing-tutorial">"Introduction to Parallel Computing Tutorial | HPC @ LLNL"</a>. <i>hpc.llnl.gov</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2024-03-21</span></span>.</cite></span>

</li>

<li id="cite_note-ParFuncProg-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-ParFuncProg_6-0">^</a></b></span> <span class="reference-text">Hammond, Kevin. Parallel functional programming: An introduction. In International Symposium on Parallel Symbolic Computation, p. 46. 1994.</span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text">McBurney, D. L., and M. Ronan Sleep. "Transputer-based experiments with the ZAPP architecture." PARLE Parallel Architectures and Languages Europe. Springer Berlin Heidelberg, 1987.</span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.mcs.anl.gov/~itf/dbpp/text/node16.html">"2.2 Partitioning"</a>. <i>www.mcs.anl.gov</i><span class="reference-accessdate">. Retrieved <span class="nowrap">2024-03-21</span></span>.</cite></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text">Skillicorn, David B., and Domenico Talia, Models and languages for parallel computation, ACM Computing Surveys, 30.2 123–169 (1998), <a rel="nofollow" class="external free" href="https://www.cs.utexas.edu/users/browne/CS392Cf2000/papers/ModelsOfParallelComputation-Skillicorn.pdf">https://www.cs.utexas.edu/users/browne/CS392Cf2000/papers/ModelsOfParallelComputation-Skillicorn.pdf</a></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Further_reading">Further reading</h2></div>

<ul><li><cite id="CITEREFBlaise_Barney" class="citation cs2">Blaise Barney, <a rel="nofollow" class="external text" href="https://web.archive.org/web/20130610122229/https://computing.llnl.gov/tutorials/parallel_comp/"><i>Introduction to Parallel Computing</i></a>, Lawrence Livermore National Laboratory, archived from <a rel="nofollow" class="external text" href="https://computing.llnl.gov/tutorials/parallel_comp/">the original</a> on 2013-06-10<span class="reference-accessdate">, retrieved <span class="nowrap">2015-11-22</span></span></cite></li>

<li><cite id="CITEREFMurray_I._Cole." class="citation cs2">Murray I. Cole., <a rel="nofollow" class="external text" href="http://homepages.inf.ed.ac.uk/mic/Pubs/skeletonbook.pdf"><i>Algorithmic Skeletons: Structured Management of Parallel Computation</i></a> <span class="cs1-format">(PDF)</span>, University of Glasgow</cite></li>

<li><cite id="CITEREFJ._DarlintonM._GhanemH._W._To1993" class="citation book cs1">J. Darlinton; M. Ghanem; H. W. To (1993). "Structured parallel programming". <a rel="nofollow" class="external text" href="https://www.researchgate.net/publication/3557907"><i>Proceedings of Workshop on Programming Models for Massively Parallel Computers</i></a>. pp. <span class="nowrap">160–</span>169. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FPMMP.1993.315543">10.1109/PMMP.1993.315543</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-8186-4900-3</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:15265646">15265646</a>.</cite></li>

<li><cite id="CITEREFIan_Foster" class="citation cs2">Ian Foster, <a rel="nofollow" class="external text" href="http://www.mcs.anl.gov/~itf/dbpp"><i>Designing and Building Parallel Programs</i></a>, Argonne National Laboratory</cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Parallel_computing346" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Parallel_computing346" style="font-size:114%;margin:0 4em"><a href="Parallel_computing" title="Parallel computing">Parallel computing</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Distributed_computing" title="Distributed computing">Distributed computing</a></li>

<li><a href="Parallel_computing" title="Parallel computing">Parallel computing</a></li>

<li><a href="Parallel_algorithm" title="Parallel algorithm">Parallel algorithm</a></li>

<li><a href="Massively_parallel" title="Massively parallel">Massively parallel</a></li>

<li><a href="Cloud_computing" title="Cloud computing">Cloud computing</a></li>

<li><a href="High-performance_computing" title="High-performance computing">High-performance computing</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li>

<li><a href="Manycore_processor" title="Manycore processor">Manycore processor</a></li>

<li><a href="General-purpose_computing_on_graphics_processing_units" title="General-purpose computing on graphics processing units">GPGPU</a></li>

<li><a href="Computer_network" title="Computer network">Computer network</a></li>

<li><a href="Systolic_array" title="Systolic array">Systolic array</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Levels</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Instruction-level_parallelism" title="Instruction-level parallelism">Instruction</a></li>

<li><a href="Task_parallelism" title="Task parallelism">Thread</a></li>

<li><a href="Memory-level_parallelism" title="Memory-level parallelism">Memory</a></li>

<li><a href="Pipeline_(computing)" title="Pipeline (computing)">Pipeline</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Multithreading_(computer_architecture)" title="Multithreading (computer architecture)">Multithreading</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Temporal_multithreading" title="Temporal multithreading">Temporal</a></li>

<li><a href="Simultaneous_multithreading" title="Simultaneous multithreading">Simultaneous</a> (SMT)</li>

<li><a href="Simultaneous_and_heterogeneous_multithreading" title="Simultaneous and heterogeneous multithreading">Simultaneous and heterogenous</a></li>

<li><a href="Speculative_multithreading" title="Speculative multithreading">Speculative</a> (SpMT)</li>

<li><a href="Preemption_(computing)" title="Preemption (computing)">Preemptive</a></li>

<li><a href="Computer_multitasking#Cooperative_multitasking" title="Computer multitasking">Cooperative</a></li>

<li><a href="Bulldozer_(microarchitecture)#Bulldozer_core" title="Bulldozer (microarchitecture)">Clustered multi-thread</a> (CMT)</li>

<li><a href="Hardware_scout" title="Hardware scout">Hardware scout</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theory</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parallel_RAM" title="Parallel RAM">PRAM model</a></li>

<li><a href="Parallel_external_memory" title="Parallel external memory">PEM model</a></li>

<li><a href="Analysis_of_parallel_algorithms" title="Analysis of parallel algorithms">Analysis of parallel algorithms</a></li>

<li><a href="Amdahl's_law" title="Amdahl's law">Amdahl's law</a></li>

<li><a href="Gustafson's_law" title="Gustafson's law">Gustafson's law</a></li>

<li><a href="Cost_efficiency" title="Cost efficiency">Cost efficiency</a></li>

<li><a href="Karp%E2%80%93Flatt_metric" title="Karp–Flatt metric">Karp–Flatt metric</a></li>

<li><a href="Parallel_slowdown" title="Parallel slowdown">Slowdown</a></li>

<li><a href="Speedup" title="Speedup">Speedup</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Elements</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Process_(computing)" title="Process (computing)">Process</a></li>

<li><a href="Thread_(computing)" title="Thread (computing)">Thread</a></li>

<li><a href="Fiber_(computer_science)" title="Fiber (computer science)">Fiber</a></li>

<li><a href="Instruction_window" title="Instruction window">Instruction window</a></li>

<li><a href="Array_(data_structure)" title="Array (data structure)">Array</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Coordination</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li>

<li><a href="Memory_coherence" title="Memory coherence">Memory coherence</a></li>

<li><a href="Cache_coherence" title="Cache coherence">Cache coherence</a></li>

<li><a href="Cache_invalidation" title="Cache invalidation">Cache invalidation</a></li>

<li><a href="Barrier_(computer_science)" title="Barrier (computer science)">Barrier</a></li>

<li><a href="Synchronization_(computer_science)" title="Synchronization (computer science)">Synchronization</a></li>

<li><a href="Application_checkpointing" title="Application checkpointing">Application checkpointing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_programming" title="Computer programming">Programming</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Stream_processing" title="Stream processing">Stream processing</a></li>

<li><a href="Dataflow_programming" title="Dataflow programming">Dataflow programming</a></li>

<li>

<ul><li><a href="Implicit_parallelism" title="Implicit parallelism">Implicit parallelism</a></li>

<li><a href="Explicit_parallelism" title="Explicit parallelism">Explicit parallelism</a></li>

<li><a href="Concurrency_(computer_science)" title="Concurrency (computer science)">Concurrency</a></li></ul></li>

<li><a href="Non-blocking_algorithm" title="Non-blocking algorithm">Non-blocking algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_hardware" title="Computer hardware">Hardware</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Flynn's_taxonomy" title="Flynn's taxonomy">Flynn's taxonomy</a>

<ul><li><a href="Single_instruction%2C_multiple_threads" title="Single instruction, multiple threads">Array processing</a> (SIMT)</li>

<li><a href="Flynn's_taxonomy#Pipelined_processor" title="Flynn's taxonomy">Pipelined processing</a></li>

<li><a href="Flynn's_taxonomy#Associative_processor" title="Flynn's taxonomy">Associative processing</a></li></ul></li>

<li><a href="Dataflow_architecture" title="Dataflow architecture">Dataflow architecture</a></li>

<li><a href="Instruction_pipelining" title="Instruction pipelining">Pipelined processor</a></li>

<li><a href="Superscalar_processor" title="Superscalar processor">Superscalar processor</a></li>

<li><a href="Vector_processor" title="Vector processor">Vector processor</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessor</a>

<ul><li><a href="Symmetric_multiprocessing" title="Symmetric multiprocessing">symmetric</a></li>

<li><a href="Asymmetric_multiprocessing" title="Asymmetric multiprocessing">asymmetric</a></li></ul></li>

<li><a href="Semiconductor_memory" title="Semiconductor memory">Memory</a>

<ul><li><a href="Shared_memory" title="Shared memory">shared</a></li>

<li><a href="Distributed_memory" title="Distributed memory">distributed</a></li>

<li><a href="Distributed_shared_memory" title="Distributed shared memory">distributed shared</a></li>

<li><a href="Massively_parallel" title="Massively parallel">Massively parallel</a> computer</li>

<li><a href="Computer_cluster" title="Computer cluster">Computer cluster</a>

<ul><li><a href="Beowulf_cluster" title="Beowulf cluster">Beowulf cluster</a></li></ul></li>

<li><a href="Grid_computing" title="Grid computing">Grid computer</a></li>

<li><a href="Hardware_acceleration" title="Hardware acceleration">Hardware acceleration</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="API" title="API">APIs</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Ateji_PX" title="Ateji PX">Ateji PX</a></li>

<li><a href="Boost_(C%2B%2B_libraries)" title="Boost (C++ libraries)">Boost</a></li>

<li><a href="Chapel_(programming_language)" title="Chapel (programming language)">Chapel</a></li>

<li><a href="Charm%2B%2B" title="Charm++">Charm++</a></li>

<li><a href="Coarray_Fortran" title="Coarray Fortran">Coarray Fortran</a></li>

<li><a href="Dryad_(programming)" title="Dryad (programming)">Dryad</a></li>

<li><a href="Global_Arrays" title="Global Arrays">Global Arrays</a></li>

<li><a href="GPUOpen" title="GPUOpen">GPUOpen</a></li>

<li><a href="OpenMP" title="OpenMP">OpenMP</a></li>

<li><a href="OpenCL" title="OpenCL">OpenCL</a></li>

<li><a href="OpenHMPP" title="OpenHMPP">OpenHMPP</a></li>

<li><a href="OpenACC" title="OpenACC">OpenACC</a></li>

<li><a href="Parallel_Extensions" title="Parallel Extensions">Parallel Extensions</a></li>

<li><a href="Pthreads" title="Pthreads">pthreads</a></li>

<li><a href="RaftLib" title="RaftLib">RaftLib</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Problems</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatic_parallelization" title="Automatic parallelization">Automatic parallelization</a></li>

<li><a href="Deadlock_(computer_science)" title="Deadlock (computer science)">Deadlock</a></li>

<li><a href="Deterministic_algorithm" title="Deterministic algorithm">Deterministic algorithm</a></li>

<li><a href="Embarrassingly_parallel" title="Embarrassingly parallel">Embarrassingly parallel</a></li>

<li><a href="Parallel_slowdown" title="Parallel slowdown">Parallel slowdown</a></li>

<li><a href="Race_condition" title="Race condition">Race condition</a></li>

<li><a href="Software_lockout" title="Software lockout">Software lockout</a></li>

<li><a href="Scalability" title="Scalability">Scalability</a></li>

<li><a href="Starvation_(computer_science)" title="Starvation (computer science)">Starvation</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Category: Parallel computing</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-05" href="https://en.wikipedia.org/wiki/?title=Parallel_programming_model&oldid=1294069603">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>